The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


6.4 S-boxes

The security of a cipher can be very sensitive to the particulars of its S-boxes: size, number, values, usage. Ciphers invented before the public discovery of differential cryptanalysis sometimes used arbitrary sources for their S-box entries.

Randomly constructed known S-boxes are unlikely to be secure. Khafre uses S-boxes taken from the RAND tables [RAND55], and it is vulnerable to differential cryptanalysis [BS92]. NewDES8 [Sco85], with S-boxes derived from the Declaration of Independence [Jeff+76], could be made much stronger with good S-boxes. DES variants with random fixed S-boxes are very likely to be weak [BS93, Mat95], and CMEA was weakened extensively because of a poor S-box choice [WSK97].


8Despite the algorithm name, NewDES is neither a DES variant nor a new algorithm based on DES.

Some cipher designers responded to this threat by carefully crafting S-boxes to resist known attacks—DES [Cop94], sn DES [KPL93, Knu93c, KLPL95], CAST [MA96, Ada97a]—while others relied on random key-dependent S-boxes for security—Khufu, Blowfish, WAKE [Whe94].9 The best existing attack on Khufu breaks 16 rounds [CC94], while the best attack on Blowfish breaks only four [Rij7]. Serpent [BAK98] reused the DES S-boxes.


9The WAKE design has several variants (Cla97, CIa98]; neither the basic algorithm nor its variants have been extensively cryptanalyzed.

GOST [GOST89] navigated a middle course: each application has different fixed S-boxes, turning them into an application-specific family key.

6.4.1 Large S-boxes

S-boxes vary in size, from GOST’s 4-by-4-bit S-boxes to Tiger’s 8-by-64-bit S-boxes [AB96b]. Large S-boxes are generally assumed to be more secure than smaller ones—a view we share—but at the price of increased storage requirements; DES’ eight 6-by-4-bit S-boxes require 256 bytes of storage, while Blowfish’s four 8-by-32-bit S-boxes require 4 Kbytes. Certainly input size matters more than output size; an 8-by-64-bit S-box can be stored in 2 Kbytes, while a 16-by-16-bit S-box requires 128 Kbytes. (Note that there is a limit to the advantages of making S-boxes bigger. S-boxes with small input size and very large output size tend to have very good linear approximations; S-boxes with sufficiently large outputs relative to input size axe guaranteed to have at least one perfect linear approximation [Bih95].)

Twofish used the same solution as Square: mid-sized S-boxes (8-by-8-bit) used to construct a large S-box (8-by-32-bit).

6.4.2 Algorithmic S-boxes

S-boxes can either be specified as large tables, like DES, Khufu/Khafre, and YLCY [YLCY98], or derived algebraically, like FEAL, LOKI89/LOKI91 (and LOKI97 [Bro98]), IDEA, and SAFER. The advantage of the former is that there is no mathematical structure that can potentially be used for cryptanalysis. The advantage of the latter is that the S-boxes are more compact, and can be more easily implemented in applications where the ROM or RAM for large tables is not available.

Algebraic S-boxes can result in S-boxes that are vulnerable to differential cryptanalysis: [Mur90] against FEAL, and [Knu93a, Knu93b] against LOKI. Higher-order differential cryptanalysis is especially powerful against algorithms with simple algebraic S-boxes [Knu95b, JK97, SMK98].

Both tabular and algebraic techniques, however, can be used to generate S-boxes with given cryptographic properties simply by testing the results of the generation algorithm. There has been much written about testing S-boxes for their resistance to different statistical attacks, starting from the work done on DES [AT90, AT93, Cop94, Ada97a, Mor98].

In Twofish we tried to do both: we chose to build our 8-by-8-bit S-boxes algorithmically out of 4-by-4-bit S-boxes. However, we chose the 4-by-4-bit S-boxes randomly and then extensively tested the resulting 8-by-8-bit S-boxes against the cryptographic properties we required. This idea is similar to the one used in CS-Cipher [SV98].

6.4.3 Key-dependent S-boxes

S-boxes are either fixed for all keys or key dependent. It is our belief that ciphers with key-dependent S-boxes are, in general, more secure than fixed S-boxes.

There axe two different philosophies regarding key-dependent S-boxes. In some ciphers, the S-box is constructed specifically to ensure that no two entries are identical—Khufu and WAKE—while others simply create the S-box randomly and hope for the best: REDOG-II [CW91] and Blowfish [Sch94]. The latter results in a simpler key schedule, but may result in weaknesses (e.g., a weakness in reduced-round variants of Blowfish [Vau96a]). Another strategy is to generate key-dependent S-boxes from a known secure S-box and a series of strict mathematical rules: e.g., Biham-DES [BB94].

Most key-dependent S-boxes are created by some process completely orthogonal to the underlying cipher. SEAL, for example, uses SHA [NIST93] to create its key-dependent S-boxes. Blowfish uses repeated iterations of it-self The results are S-boxes that axe effectively random, but the cost is an enormous performance penalty in key setup time.10


10For example, setting up a single Blowfish key takes as much time as encrypting 520 blocks, or 4160 bytes, of data.

An alternative is to build the S-boxes using fairly simple key-dependent operations from fixed S-boxes. This results in a much faster key setup, but unless the creation algorithm is extensively cryptanalyzed together with the encryption algorithm, unwanted synergies could lead to attacks on the resulting cipher.

To avoid differential (as well as high-order differential, linear, and related-key) attacks, we made the small S-boxes key dependent. It is our belief that while random key-dependent S-boxes can offer acceptable security if used correctly, the benefits of a surjective S-box are worth the additional complexities that constructing them entails. So, to avoid attacks based on non-surjective round functions [BB95, RP95b, RPD97, CWSK98], we made the 8-by-8-bit S-boxes bijective.

This construction is similar to Skipjack’s use of a single fixed 8-by-8-bit S-box, four key bytes, and a 4-round Feistel structure to create five different 16-by-16-bit key-dependent S-boxes [NSA98].

However, there is really no such thing as a key-dependent S-box. Twofish uses a complex multi-stage series of S-boxes and round subkeys that are often precomputed as key-dependent S-boxes for efficiency purposes. (For example, see Figure 4.3 on page 18.) We often used this conceptualization. when carrying out our own cryptanalysis against Twofish.


Previous Table of Contents Next